package main

// 300. 最长上升子序列
// https://leetcode-cn.com/problems/longest-increasing-subsequence/

// 给定一个无序的整数数组，找到其中最长上升子序列的长度。

func lengthOfLIS(nums []int) int {
	if len(nums) < 1 {
		return 0
	}
	maxSum := 1
	dp := make([]int, len(nums))
	for i, n := range nums {
		dp[i] = 1
		for j, m := range nums[:i] {
			if n <= m {
				continue
			}
			dp[i] = max(dp[i], dp[j]+1)
			maxSum = max(maxSum, dp[i])
		}
	}
	return maxSum
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	//req := lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18})
	req := lengthOfLIS([]int{1, 3, 6, 7, 9, 4, 10, 5, 6})
	println(req)

}
